package _动态规划系列._博弈问题;

/**
 * @Author: 吕庆龙
 * @Date: 2020/4/2 16:11
 * <p>
 * 功能描述:
 */
public class Summary_0887 {

    public static void main(String[] args) {
        Summary_0887 test = new Summary_0887();
        int[] piles = new int[]{5,3,4,5};
        test.stoneGame(piles);

    }

    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        Pair[][] dp = new Pair[n][n];

        for (int i = 0; i < n; i++)
            for (int j = i; j < n; j++)
                dp[i][j] = new Pair(0, 0);

        //base case i==j的时候  先手有piles[i]分,后手0分
        for (int i = 0; i < n; i++) {
            dp[i][i].fir = piles[i];
            dp[i][i].sec = 0;
        }

        int j = 0;
        //要斜着遍历dp table
        for (int l = 2; l <= n; l++) { //l表示斜着的层数,base case是第一层，所以这里从第2层开始
            for (int i = 0; i <= n - l; i++) {  //这个就是行标
                j = l + i - 1;

                int left = piles[i] + dp[i + 1][j].sec;  //先手选左边的石子堆
                int right = piles[j] + dp[i][j - 1].sec; //先手选右边的石子堆

                if (left > right) {
                    dp[i][j].fir = left;
                    dp[i][j].sec = dp[i + 1][j].fir;
                } else {
                    dp[i][j].fir = right;
                    dp[i][j].sec = dp[i][j - 1].fir;
                }
            }
        }
        int res = dp[0][n - 1].fir - dp[0][n - 1].sec;

        return res > 0 ? true : false;
    }
}
